package com.leetcode.linkedList;

import com.leetcode.basic.ListNode;

/**
 * @author Dennis Li
 * @date 2020/9/8 17:24
 */
public class DetectCycle_142 {

    public ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;

        do {
            if (fast == null || fast.next == null)
                return null;
            fast = fast.next.next;
            slow = slow.next;
        } while (slow != fast);

        fast = head;
        while (slow != fast) {
            // slow 会在圈内走N圈 + S2长度
            slow = slow.next;
            fast = fast.next;
        }

        return slow;
    }

}
